package date_202403

//1044. 最长重复子串
//给你一个字符串 s ，考虑其所有 重复子串 ：即 s 的（连续）子串，在 s 中出现 2 次或更多次。这些出现之间可能存在重叠。
//
//返回 任意一个 可能具有最长长度的重复子串。如果 s 不含重复子串，那么答案为 "" 。
//
//示例 1：
//
//输入：s = "banana"
//输出："ana"
//示例 2：
//
//输入：s = "abcd"
//输出：""
//
//
//提示：
//
//2 <= s.length <= 3 * 10^4
//s 由小写英文字母组成

func longestDupSubstring(s string) string {
	if len(s) <= 1 {
		return ""
	}

	maxLenStr := ""
	left, right := 1, len(s)
	for left < right {
		i := (left + right) / 2

		hasRepeatStr := false
		curHash := make(map[string]struct{})
		for j := 0; j < len(s)-i+1; j++ {
			curStr := s[j : j+i]
			if _, ok := curHash[curStr]; ok {
				if len(curStr) > len(maxLenStr) {
					maxLenStr = curStr
				}
				hasRepeatStr = true
				break
			}
			curHash[curStr] = struct{}{}
		}

		if hasRepeatStr {
			left = i + 1
		} else {
			right = i - 1
		}
	}
	return maxLenStr
}
